#!/usr/bin/env/python3
# -*- coding: utf-8 -*-

"""
@Time    : 2020/3/12 20:11
@Author  : Chen Liu
@FileName: shuzu.py
@Software: PyCharm
"""
# 小美曾经有一个特殊的数组，这个数组的长度为n。但是她在打恐怖游戏的时候被吓得忘记了这个数组长什么样了。不过她还记得这个数组满足一些条件。
# 首先这个数组的每个数的范围都在L和R之间。包括端点。
# 除此之外，这个数组满足数组中的所有元素的和是k的倍数。
# 但是这样的数组太多了，小美想知道有多少个这样的数组。你只需要告诉她在模1e9+7意义下的答案就行了。
# 一行四个整数n,k,L,R
# （1≤n≤1e5    1≤k≤10    1≤L≤R≤1e9）
# 输出
# 输出一个数表示满足条件的数组的个数。

# 参考链接：https://www.nowcoder.com/discuss/380908?type=2&order=0&pos=2&page=1
# 思路:动态规划


def count_num(n, k, L, R):
    if n < k:
        return 0
    if L < R:
        return 0


